package com.u17;

/**
 * @author u17
 * https://leetcode-cn.com/problems/maximum-subarray/
 */
public class Solution {

    /**
     * 当前数加上之前的数的和跟当前数作比较
     * 如果当前数比较大，那就返回当前数
     * 如果是和大，那几返回和
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {

        int pre = 0, maxAns = nums[0];
        for (int i : nums) {
            // 比较本身和前面相加的哪个大
            pre = Math.max(pre + i, i);
            // 找出之前的大还是现在的大，返回最大的
            maxAns = Math.max(maxAns, pre);
        }

        return maxAns;
    }




    public int maxSubArray2(int[] nums) {

        int n = 0;

        int sum = nums[0];

        for (int x : nums) {
            n = Math.max(n + x, x);
            sum = Math.max(sum, n);
        }

        return sum;
    }

}
